We study the problem of augmenting online algorithms with machine learned (ML) advice. In particular, we consider the \emph{multi-shop ski rental} (MSSR) problem, which is a generalization of the classical ski rental problem. In MSSR, each shop has different prices for buying and renting a pair of skis, and a skier has to make decisions on when and where to buy. We obtain both deterministic and randomized online algorithms with provably improved performance when either a single or multiple ML predictions are used to make decisions. These online algorithms have no knowledge about the quality or the prediction error type of the ML prediction. The performance of these online algorithms are robust to the poor performance of the predictors, but improve with better predictions. Extensive experiments using both synthetic and real world data traces verify our theoretical observations and show better performance against algorithms that purely rely on online decision making.

Additional Feedback: Other comments: The MSSR problem mandates that the skier first chooses a shop and then must rent / buy at that same shop for the entire instance. Without this restriction the problem boils down to the standard ski rental problem with rent cost r_i and buy cost b_n since the algorithm can always rent from shop 1 and buy from shop n. It will be good to emphasize the importance of this restriction more in the model. In Lemma 1, the best deterministic online algorithm can choose any of the n shops depending on the argmin of specified term. However, both the randomized and deterministic algorithms that utilize the predictions only buy from either the first shop or the last shop.

This paper builds on prior work for the ski rental problem using predictions. There is interest in this model of online algorithm analysis in the NuerIPS community. However, the paper does not give a lot of new technical insights. I believe this is a borderline paper. It offers a marginal improvement on an area of interest.

We study the problem of augmenting online algorithms with machine learned (ML) advice. In particular, we consider the \emph{multi-shop ski rental} (MSSR) problem, which is a generalization of the classical ski rental problem. In MSSR, each shop has different prices for buying and renting a pair of skis, and a skier has to make decisions on when and where to buy. We obtain both deterministic and randomized online algorithms with provably improved performance when either a single or multiple ML predictions are used to make decisions. These online algorithms have no knowledge about the quality or the prediction error type of the ML prediction.